package org.apache.maven.project;

/*
 * Licensed to the Apache Software Foundation (ASF) under one
 * or more contributor license agreements.  See the NOTICE file
 * distributed with this work for additional information
 * regarding copyright ownership.  The ASF licenses this file
 * to you under the Apache License, Version 2.0 (the
 * "License"); you may not use this file except in compliance
 * with the License.  You may obtain a copy of the License at
 *
 *  http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing,
 * software distributed under the License is distributed on an
 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
 * KIND, either express or implied.  See the License for the
 * specific language governing permissions and limitations
 * under the License.
 */

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;

import org.apache.maven.artifact.ArtifactUtils;
import org.apache.maven.model.Dependency;
import org.apache.maven.model.Extension;
import org.apache.maven.model.Parent;
import org.apache.maven.model.Plugin;
import org.codehaus.plexus.util.StringUtils;
import org.codehaus.plexus.util.dag.CycleDetectedException;
import org.codehaus.plexus.util.dag.DAG;
import org.codehaus.plexus.util.dag.TopologicalSorter;
import org.codehaus.plexus.util.dag.Vertex;

public class ProjectSorter {
  private DAG dag;

  private List<MavenProject> sortedProjects;

  private Map<String, MavenProject> projectMap;

  private MavenProject topLevelProject;

  /**
   * Sort a list of projects.
   * <ul>
   * <li>collect all the vertices for the projects that we want to build.</li>
   * <li>iterate through the deps of each project and if that dep is within the set of projects we
   * want to build then add an edge, otherwise throw the edge away because that dependency is not
   * within the set of projects we are trying to build. we assume a closed set.</li>
   * <li>do a topo sort on the graph that remains.</li>
   * </ul>
   * 
   * @throws DuplicateProjectException if any projects are duplicated by id
   */
  // MAVENAPI FIXME: the DAG used is NOT only used to represent the dependency relation,
  // but also for <parent>, <build><plugin>, <reports>. We need multiple DAG's
  // since a DAG can only handle 1 type of relationship properly.
  // Usecase: This is detected as a cycle:
  // org.apache.maven:maven-plugin-api -(PARENT)->
  // org.apache.maven:maven -(inherited REPORTING)->
  // org.apache.maven.plugins:maven-checkstyle-plugin -(DEPENDENCY)->
  // org.apache.maven:maven-plugin-api
  // In this case, both the verify and the report goals are called
  // in a different lifecycle. Though the compiler-plugin has a valid usecase, although
  // that seems to work fine. We need to take versions and lifecycle into account.
  public ProjectSorter(List<MavenProject> projects) throws CycleDetectedException, DuplicateProjectException {
    dag = new DAG();

    // groupId:artifactId:version -> project
    projectMap = new HashMap<String, MavenProject>(projects.size() * 2);

    // groupId:artifactId -> (version -> vertex)
    Map<String, Map<String, Vertex>> vertexMap = new HashMap<String, Map<String, Vertex>>(projects.size() * 2);

    for (MavenProject project : projects) {
      String projectId = getId(project);

      MavenProject conflictingProject = projectMap.put(projectId, project);

      if (conflictingProject != null) {
        throw new DuplicateProjectException(projectId, conflictingProject.getFile(), project.getFile(),
            "Project '" + projectId + "' is duplicated in the reactor");
      }

      String projectKey = ArtifactUtils.versionlessKey(project.getGroupId(), project.getArtifactId());

      Map<String, Vertex> vertices = vertexMap.get(projectKey);
      if (vertices == null) {
        vertices = new HashMap<String, Vertex>(2, 1);
        vertexMap.put(projectKey, vertices);
      }
      vertices.put(project.getVersion(), dag.addVertex(projectId));
    }

    for (Vertex projectVertex : (List<Vertex>) dag.getVerticies()) {
      String projectId = projectVertex.getLabel();

      MavenProject project = projectMap.get(projectId);

      for (Dependency dependency : project.getDependencies()) {
        addEdge(projectMap, vertexMap, project, projectVertex, dependency.getGroupId(), dependency.getArtifactId(),
            dependency.getVersion(), false, false);
      }

      Parent parent = project.getModel().getParent();

      if (parent != null) {
        // Parent is added as an edge, but must not cause a cycle - so we remove any other edges it
        // has
        // in conflict
        addEdge(projectMap, vertexMap, null, projectVertex, parent.getGroupId(), parent.getArtifactId(),
            parent.getVersion(), true, false);
      }

      List<Plugin> buildPlugins = project.getBuildPlugins();
      if (buildPlugins != null) {
        for (Plugin plugin : buildPlugins) {
          addEdge(projectMap, vertexMap, project, projectVertex, plugin.getGroupId(), plugin.getArtifactId(),
              plugin.getVersion(), false, true);

          for (Dependency dependency : plugin.getDependencies()) {
            addEdge(projectMap, vertexMap, project, projectVertex, dependency.getGroupId(), dependency.getArtifactId(),
                dependency.getVersion(), false, true);
          }
        }
      }

      List<Extension> buildExtensions = project.getBuildExtensions();
      if (buildExtensions != null) {
        for (Extension extension : buildExtensions) {
          addEdge(projectMap, vertexMap, project, projectVertex, extension.getGroupId(), extension.getArtifactId(),
              extension.getVersion(), false, true);
        }
      }
    }

    List<MavenProject> sortedProjects = new ArrayList<MavenProject>(projects.size());

    List<String> sortedProjectLabels = TopologicalSorter.sort(dag);

    for (String id : sortedProjectLabels) {
      sortedProjects.add(projectMap.get(id));
    }

    this.sortedProjects = Collections.unmodifiableList(sortedProjects);
  }

  private void addEdge(Map<String, MavenProject> projectMap, Map<String, Map<String, Vertex>> vertexMap,
      MavenProject project, Vertex projectVertex, String groupId, String artifactId, String version, boolean force,
      boolean safe) throws CycleDetectedException {
    String projectKey = ArtifactUtils.versionlessKey(groupId, artifactId);

    Map<String, Vertex> vertices = vertexMap.get(projectKey);

    if (vertices != null) {
      if (isSpecificVersion(version)) {
        Vertex vertex = vertices.get(version);
        if (vertex != null) {
          addEdge(projectVertex, vertex, project, projectMap, force, safe);
        }
      } else {
        for (Vertex vertex : vertices.values()) {
          addEdge(projectVertex, vertex, project, projectMap, force, safe);
        }
      }
    }
  }

  private void addEdge(Vertex fromVertex, Vertex toVertex, MavenProject fromProject,
      Map<String, MavenProject> projectMap, boolean force, boolean safe) throws CycleDetectedException {
    if (fromVertex.equals(toVertex)) {
      return;
    }

    if (fromProject != null) {
      MavenProject toProject = projectMap.get(toVertex.getLabel());
      fromProject.addProjectReference(toProject);
    }

    if (force && toVertex.getChildren().contains(fromVertex)) {
      dag.removeEdge(toVertex, fromVertex);
    }

    try {
      dag.addEdge(fromVertex, toVertex);
    } catch (CycleDetectedException e) {
      if (!safe) {
        throw e;
      }
    }
  }

  private boolean isSpecificVersion(String version) {
    return !(StringUtils.isEmpty(version) || version.startsWith("[") || version.startsWith("("));
  }

  // TODO: !![jc; 28-jul-2005] check this; if we're using '-r' and there are aggregator tasks, this
  // will result in weirdness.
  public MavenProject getTopLevelProject() {
    if (topLevelProject == null) {
      for (Iterator<MavenProject> i = sortedProjects.iterator(); i.hasNext() && (topLevelProject == null);) {
        MavenProject project = i.next();
        if (project.isExecutionRoot()) {
          topLevelProject = project;
        }
      }
    }

    return topLevelProject;
  }

  public List<MavenProject> getSortedProjects() {
    return sortedProjects;
  }

  public boolean hasMultipleProjects() {
    return sortedProjects.size() > 1;
  }

  public List<String> getDependents(String id) {
    return dag.getParentLabels(id);
  }

  public List<String> getDependencies(String id) {
    return dag.getChildLabels(id);
  }

  public static String getId(MavenProject project) {
    return ArtifactUtils.key(project.getGroupId(), project.getArtifactId(), project.getVersion());
  }

  public DAG getDAG() {
    return dag;
  }

  public Map<String, MavenProject> getProjectMap() {
    return projectMap;
  }

}
